import java.awt.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;

/*
 * http://www.policyalmanac.org/games/aStarTutorial.htm
 */

public class AStarGrid extends GridMap {
	
	List<AStarNode> open = new ArrayList<AStarNode>();
	List<AStarNode> closed = new ArrayList<AStarNode>();
	
	public AStarGrid(int x, int y, int width, int height, int resolution) throws Exception {
		super(x, y, width, height, resolution);
	}
	
	public List<Point> getPath(Point start, Point end) {
		return getPath(start, end, true);
	}
	
	public List<Point> getPath(Point start, Point end, boolean reverse) {
		
		// First clear the lists
		open.clear();
		closed.clear();
		
		// Check if start is blocked
		if(grid[start.x][start.y])
			return null;
		
		// This is the current node
		AStarNode tmp;
		
		// Begin by adding start to our open list
		tmp = new AStarNode(start, null, 0, end);
		open.add(tmp);
		
		// Loop through open list until end is reached
		while(tmp.h != 0 && ( !grid[end.x][end.y] || tmp.h > 10 )) {
		
			// Get start-node nodes
			for(int y = -1; y < 2; y++) {
				for(int x = -1; x < 2; x++) {
					int newx = tmp.grid_pos.x + x;
					int newy = tmp.grid_pos.y + y;
					
					// Check lists
						boolean cont = false;
						ListIterator<AStarNode> it = open.listIterator();
						while(it.hasNext()) {
							AStarNode a = it.next();
							if(a.grid_pos.x == newx && a.grid_pos.y == newy) {
								cont = true;
								break;
							}
						}
						
						if(cont)
							continue;
						
						it = closed.listIterator();
						while(it.hasNext()) {
							AStarNode a = it.next();
							if(a.grid_pos.x == newx && a.grid_pos.y == newy) {
								cont = true;
								break;
							}
						}
						
						if(cont)
							continue;
					// End check lists
					
					if(newx < 0 ||
					   newy < 0 ||
					   newx >= grid_max_x ||
					   newy >= grid_max_y ||
					   grid[newx][newy])
						continue;				// If one statement is true: just ignore
					else {
						if(x != 0 && y != 0) {	// If diagonal costs 14
							if(!grid[newx-x][newy] && !grid[newx][newy-y]) // If the diagonal way isn't blocked
								open.add(new AStarNode(new Point(newx, newy), tmp, 14, end));
						}
						else					// Else costs 10
							open.add(new AStarNode(new Point(newx, newy), tmp, 10, end));
					}
				}
			}
			
			// Move start to closed
			open.remove(tmp);
			closed.add(tmp);
			
			// Get next node with best f value
			ListIterator<AStarNode> it = open.listIterator();
			
			if(!it.hasNext()) {
				// Search the smallest h in closed
				it = closed.listIterator();
				while(it.hasNext()) {
					AStarNode a = it.next();
					if(tmp.h > a.h)
						tmp = a;
				}
				
				List<Point> retlist = new ArrayList<Point>();
				
				// Go through nodes until we reached the start node
				while(tmp.parent != null) {
					retlist.add(tmp.grid_pos);
					tmp = tmp.parent;
				}
				
				if(reverse)
					Collections.reverse(retlist);
				return retlist;
			}
			
			tmp = it.next();
			while(it.hasNext()) {
				AStarNode a = it.next();
				if(tmp.f > a.f)
					tmp = a;
			}
			
		} // End Loop
		
		List<Point> retlist = new ArrayList<Point>();
		
		// Go through nodes until we reached the start node
		while(tmp != null) {
			retlist.add(tmp.grid_pos);
			tmp = tmp.parent;
		}
		
		if(reverse)
			Collections.reverse(retlist);
		return retlist;
	}
	
	public void drawChecked(Graphics2D g2d, boolean text) {
		ListIterator<AStarNode> it = open.listIterator();
		AStarNode a = null;
		while(it.hasNext()) {
			try {
				a = it.next();
				g2d.setColor(new Color(200, 200, 200));
				if(a != null)
					fillTile(g2d, a.grid_pos.x, a.grid_pos.y);
			} catch(Exception e) {}
		}
		
		if(text) {
			while(it.hasPrevious()) {
				a = it.previous();
				g2d.setColor(new Color(0, 0, 0));
				g2d.drawString(new String("F: " + (int)a.f), grid_x+a.grid_pos.x*grid_resolution+2, grid_y+a.grid_pos.y*grid_resolution+12);
				g2d.drawString(new String("G: " + (int)a.g), grid_x+a.grid_pos.x*grid_resolution+2, grid_y+a.grid_pos.y*grid_resolution+24);
				g2d.drawString(new String("H: " + (int)a.h), grid_x+a.grid_pos.x*grid_resolution+2, grid_y+a.grid_pos.y*grid_resolution+36);
			}
		}
		
		it = closed.listIterator();
		while(it.hasNext()) {
			try {
				a = it.next();
				g2d.setColor(new Color(150, 150, 150));
				if(a != null)
					fillTile(g2d, a.grid_pos.x, a.grid_pos.y);
			} catch(Exception e) {}
		}
		
		if(text) {
			while(it.hasPrevious()) {
				a = it.previous();
				g2d.setColor(new Color(0, 0, 0));
				g2d.drawString(new String("F: " + (int)a.f), grid_x+a.grid_pos.x*grid_resolution+2, grid_y+a.grid_pos.y*grid_resolution+12);
				g2d.drawString(new String("G: " + (int)a.g), grid_x+a.grid_pos.x*grid_resolution+2, grid_y+a.grid_pos.y*grid_resolution+24);
				g2d.drawString(new String("H: " + (int)a.h), grid_x+a.grid_pos.x*grid_resolution+2, grid_y+a.grid_pos.y*grid_resolution+36);
			}
		}
	}

}
